package 集合;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.List;

public class No1178猜字谜 {

    /**
     * 外国友人仿照中国字谜设计了一个英文版猜字谜小游戏，请你来猜猜看吧。
     * 字谜的迷面 puzzle 按字符串形式给出，如果一个单词 word 符合下面两个条件，那么它就可以算作谜底：
     * 单词 word 中包含谜面 puzzle 的第一个字母。
     * 单词 word 中的每一个字母都可以在谜面 puzzle 中找到。
     * 例如，如果字谜的谜面是 "abcdefg"，那么可以作为谜底的单词有 "faced", "cabbage", 和 "baggage"；而 "beefed"（不含字母 "a"）以及 "based"（其中的 "s" 没有出现在谜面中）都不能作为谜底。
     * 返回一个答案数组 answer，数组中的每个元素 answer[i] 是在给出的单词列表 words 中可以作为字谜迷面 puzzles[i] 所对应的谜底的单词数目。
     *
     * 示例：
     * 输入：
     * words = ["aaaa","asas","able","ability","actt","actor","access"],
     * puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]
     * 输出：[1,1,3,2,4,0]
     * 解释：
     * 1 个单词可以作为 "aboveyz" 的谜底 : "aaaa"
     * 1 个单词可以作为 "abrodyz" 的谜底 : "aaaa"
     * 3 个单词可以作为 "abslute" 的谜底 : "aaaa", "asas", "able"
     * 2 个单词可以作为 "absoryz" 的谜底 : "aaaa", "asas"
     * 4 个单词可以作为 "actresz" 的谜底 : "aaaa", "asas", "actt", "access"
     * 没有单词可以作为 "gaswxyz" 的谜底，因为列表中的单词都不含字母 'g'。
     *  
     * 提示：
     * 1 <= words.length <= 10^5
     * 4 <= words[i].length <= 50
     * 1 <= puzzles.length <= 10^4
     * puzzles[i].length == 7
     * words[i][j], puzzles[i][j] 都是小写英文字母。
     * 每个 puzzles[i] 所包含的字符都不重复。
     */

    //暴力超时 10^5 10^4     略过
    public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {

        int[][] wordsArr=new int[words.length][26];

        for (int i = 0; i < words.length; i++) {
            String str=words[i];
            for (int j = 0; j < str.length(); j++) {
                wordsArr[i][str.charAt(j)-'a']++;
            }
        }

        int[][] puzzlesArr=new int[puzzles.length][26];

        for (int i = 0; i < puzzles.length; i++) {
            String str=puzzles[i];//puzzles字符不会重复
            for (int j = 0; j < str.length(); j++) {
                puzzlesArr[i][str.charAt(j)-'a']++;
            }
        }

        List<Integer> result=new ArrayList<>();

        for (int i = 0; i < puzzlesArr.length; i++) {
            int count=0;
            for (int j = 0; j < wordsArr.length; j++) {
                //需要两个条件都符合
                //1.word包含puzzle的首字母
                if(wordsArr[j][puzzles[i].charAt(0)-'a']<=0){
                    //word中不包含puzzle的首字母
                    continue;
                }
                for (int k = 0; k < 26; k++) {
                    //2.word中的每个词都能在puzzle中找到
                    if(wordsArr[j][k]!=0&&puzzlesArr[i][k]==0){
                        //有一个找不到
                        break;
                    }
                    if(k==25){
                        count++;
                    }
                }
            }
            result.add(count);
        }

        return result;
    }

    public static void main(String[] args) {
        String[] str1={"aaaa","asas","able","ability","actt","actor","access"};
        String[] str2={"aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"};
        No1178猜字谜 n=new No1178猜字谜();
        List<Integer> result = n.findNumOfValidWords(str1, str2);
        System.out.println(JSON.toJSONString(result));
    }



}
